package demo2;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:二叉树的基本操作
 * User: 石方旭
 * Date: 2022-06-24
 * Time: 6:26
 */
public class BinaryTree {

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    //根节点
    public TreeNode root;

    public TreeNode createTree(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node1.left = node2;
        node1.right = node4;
        node2.left = node3;
        node2.right = node7;
        node4.left = node5;
        node4.right= node6;
        root =node1;
        return root;

    }

    // 前序遍历-->递归版本无list
    void preOrder(TreeNode root){
        if(root==null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root){
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //使用list遍历思路去存储-->前序遍历
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    //使用list子问题思路进行前序遍历
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        list.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        if(leftTree!=null){
            list.addAll(leftTree);
        }
        List<Integer> rightTree = preorderTraversal(root.right);
        if(rightTree!=null){
            list.addAll(rightTree);
        }
        return list;
    }
    //前序遍历-->非递归版本
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||(!stack.isEmpty())){
            while(cur!=null){
                stack.push(cur);
                ret.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            if(top.right!=null){
                cur = top.right;
            }
        }
        return ret;
    }

    //使用list-->子问题进行中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        List<Integer> leftTree = inorderTraversal(root.left);
        if(leftTree!=null){
            ret.addAll(leftTree);
        }
        ret.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        if(rightTree!=null){
            ret.addAll(rightTree);
        }
        return ret;
    }

    //使用list进行非递归实现--->中序遍历
    public List<Integer> inorderTraversalNor(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||!stack.isEmpty()){
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            ret.add(top.val);
            if (top.right != null) {
                cur = top.right;
            }
        }
        return ret;
    }

    //使用非递归来实现二叉树的后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null||(!stack.isEmpty())){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right==null||top.right==prev){
                stack.pop();
                ret.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return ret;
    }

    // 获取树中节点的个数-->子问题思路
    int size(TreeNode root){
        if(root==null) return 0;
        int left = size(root.left);
        int right = size(root.right);
        return left+right+1;
    }

    // 获取叶子节点的个数-->子问题思路
    int getLeafNodeCount(TreeNode root){
        if(root==null) return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        int left = getLeafNodeCount(root.left);
        int right = getLeafNodeCount(root.right);
        return left+right;
    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        if(root==null) return 0;
        if(k==1) return 1;
        int left = getKLevelNodeCount(root.left,k-1);
        int right = getKLevelNodeCount(root.right,k-1);
        return left + right;
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root){
        if(root==null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left>right?left+1:right+1;
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val){
        if(root==null) return null;
        if(root.val==val) return root;
        TreeNode leftTree = find(root.left,val);
        if(leftTree!=null){
            return leftTree;
        }
        TreeNode rightTree = find(root.right,val);
        if(rightTree!=null){
            return rightTree;
        }
        return null;
    }
    //层序遍历
    void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur==null){
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while(!queue.isEmpty()){
            TreeNode tmp =queue.peek();
            if(tmp!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }
    //深度优先搜索
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //结构上相同
        //节点值相同
        //有一棵树是空树肯定是两个不相同的树
        if((p==null&&q!=null)||(q==null&&p!=null))return false;
        if(p==null&&q==null) return true;
        if(p.val!=q.val) return false;
        //左树是否是相同的树，右树是否是相同的树
        //左树和右树都符合才是相同的树
        boolean flag1 = isSameTree(p.left,q.left);
        boolean flag2 = isSameTree(p.right,q.right);
        return flag1&&flag2;
    }
    public boolean isBalanced(TreeNode root) {
          return false;
    }

    public int height1(TreeNode root){
        if(root==null) return 0;
        int left = height1(root.left);
        int right = height1(root.right);
        if(left>=0&&right>=0&&Math.abs(left-right)<=1){
            //满足
            return left>right?left+1:right+1;
        }else {
            return -1;
        }
    }
    public boolean isBalanced1(TreeNode root) {
        if(root==null) return true;
        return height1(root)>=0;
    }


    public int preIndex = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int ib,int ie){
        if(ie<ib){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //在中序数组中查找这个根节点来确定根
        int rootIndex = findRootNode(preorder,inorder,ib,ie);
        preIndex++;//创建下一个根节点
        root.left = buildTreeChild(preorder,inorder,ib,rootIndex-1);//创建左子树
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,ie);//创建右子树
        return root;
    }

    public int findRootNode(int[] preorder, int[] inorder,int ib,int ie){
        for(int i = ib;i<=ie;++i){
            if(preorder[preIndex]==inorder[i]){
                return i;
            }
        }
        return -1;
    }
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        //先序确定根
//        return buildTreeChild(preorder,inorder,0,inorder.length-1);
//    }
//
//    public int postIndex =0;
//    public TreeNode buildTreeChild(int[] inorder, int[] postorder, int ib, int ie){
//        if(ie<ib){
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[postIndex]);
//        int rootIndex = findRootNode(inorder,postorder,ib,ie);
//        postIndex--;
//        root.left = buildTreeChild(inorder,postorder,ib,rootIndex-1);
//        root.right =  buildTreeChild(inorder,postorder,rootIndex+1,ie);
//        return root;
//    }
//
//    public int findRootNode(int[] inorder, int[] postorder,int ib,int ie){
//        for(int i =ib;i<=ie;++i){
//            if(postorder[postIndex]==inorder[i]){
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        //根据后序遍历postIndex--来一一确定根
//        postIndex = postorder.length-1;
//        return buildTreeChild(inorder,postorder,0,inorder.length-1);
//    }




}
